public class ReverseLinkedList2 {

     class Solution {
        public ListNode reverseBetween(ListNode head, int left, int right) {
            // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
            ListNode dummyHead=new ListNode(-1);
            dummyHead.next=head;

            ListNode pre=dummyHead;
            // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
            // 建议写在 for 循环里，语义清晰
            for(int i=1;i<left;i++){
                pre=pre.next;
            }
            // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
            ListNode rightNode=pre;
            for(int i=left;i<right+1;i++){
                rightNode=rightNode.next;
            }

            // 第 3 步：切断出一个子链表（截取链表）
            ListNode leftNode=pre.next;
            ListNode curr=rightNode.next;
            // 注意：切断链接
            pre.next=null;
            rightNode.next=null;
            // 第 4 步：同第 206 题，反转链表的子区间
            reverseList(leftNode);
            // 第 5 步：接回到原来的链表中
            pre.next=rightNode;
            leftNode.next=curr;
            return dummyHead.next;
        }
           ListNode reverseList(ListNode head) {
            if(head==null||head.next==null) return head;
            ListNode node=reverseList(head.next);
            head.next.next=head;
            head.next=null;
            return node;
        }
    }
}
